{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Count Ways to Build Rooms in an Ant Colony"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #graph #topological-sort #math #dynamic-programming #combinatorics"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #图 #拓扑排序 #数学 #动态规划 #组合数学"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: waysToBuildRooms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #统计为蚁群构筑房间的不同顺序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>你是一只蚂蚁，负责为蚁群构筑 <code>n</code> 间编号从 <code>0</code> 到 <code>n-1</code> 的新房间。给你一个 <strong>下标从 0 开始</strong> 且长度为 <code>n</code> 的整数数组&nbsp;<code>prevRoom</code> 作为扩建计划。其中，<code>prevRoom[i]</code> 表示在构筑房间 <code>i</code> 之前，你必须先构筑房间 <code>prevRoom[i]</code> ，并且这两个房间必须 <strong>直接</strong> 相连。房间 <code>0</code> 已经构筑完成，所以 <code>prevRoom[0] = -1</code> 。扩建计划中还有一条硬性要求，在完成所有房间的构筑之后，从房间 <code>0</code> 可以访问到每个房间。</p>\n",
    "\n",
    "<p>你一次只能构筑 <strong>一个</strong> 房间。你可以在 <strong>已经构筑好的</strong> 房间之间自由穿行，只要这些房间是 <strong>相连的</strong> 。如果房间&nbsp;<code>prevRoom[i]</code> 已经构筑完成，那么你就可以构筑房间 <code>i</code>。</p>\n",
    "\n",
    "<p>返回你构筑所有房间的 <strong>不同顺序的数目</strong> 。由于答案可能很大，请返回对 <code>10<sup>9</sup> + 7</code> <strong>取余</strong> 的结果。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/06/19/d1.JPG\" style=\"width: 200px; height: 212px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong><code>prevRoom</code> = [-1,0,1]\n",
    "<strong>输出：</strong>1\n",
    "<strong>解释：</strong>仅有一种方案可以完成所有房间的构筑：0 → 1 → 2\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "<strong><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/06/19/d2.JPG\" style=\"width: 200px; height: 239px;\" /></strong>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong><code>prevRoom</code> = [-1,0,0,1,2]\n",
    "<strong>输出：</strong>6\n",
    "<strong>解释：\n",
    "</strong>有 6 种不同顺序：\n",
    "0 → 1 → 3 → 2 → 4\n",
    "0 → 2 → 4 → 1 → 3\n",
    "0 → 1 → 2 → 3 → 4\n",
    "0 → 1 → 2 → 4 → 3\n",
    "0 → 2 → 1 → 3 → 4\n",
    "0 → 2 → 1 → 4 → 3\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == prevRoom.length</code></li>\n",
    "\t<li><code>2 &lt;= n &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>prevRoom[0] == -1</code></li>\n",
    "\t<li>对于所有的&nbsp;<code>1 &lt;= i &lt; n</code>&nbsp;，都有&nbsp;<code>0 &lt;= prevRoom[i] &lt; n</code></li>\n",
    "\t<li>题目保证所有房间都构筑完成后，从房间 <code>0</code> 可以访问到每个房间</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [count-ways-to-build-rooms-in-an-ant-colony](https://leetcode.cn/problems/count-ways-to-build-rooms-in-an-ant-colony/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [count-ways-to-build-rooms-in-an-ant-colony](https://leetcode.cn/problems/count-ways-to-build-rooms-in-an-ant-colony/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[-1,0,1]', '[-1,0,0,1,2]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "kmod = 10**9 + 7\n",
    "class Solution:\n",
    "    def waysToBuildRooms(self, prevRoom: List[int]) -> int:\n",
    "        n = len(prevRoom)\n",
    "        g = [[] for _ in range(n)]\n",
    "        for i, p in enumerate(prevRoom):\n",
    "            if p != -1:\n",
    "                g[p].append(i)\n",
    "\n",
    "        def dfs(idx):\n",
    "            if not g[idx]:\n",
    "                return 1, 1\n",
    "            \n",
    "            s, t = 1, 0\n",
    "            for ch in g[idx]:\n",
    "                a, b = dfs(ch)\n",
    "                t += b\n",
    "                s *= a * comb(t, b)\n",
    "                s %= kmod\n",
    "            return s, t + 1\n",
    "\n",
    "        return dfs(0)[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToBuildRooms(self, prevRoom: List[int]) -> int:\n",
    "        son = [[] for _ in range(len(prevRoom))]\n",
    "        for i in range(1, len(prevRoom)):\n",
    "            son[prevRoom[i]].append(i)\n",
    "        def dfs(x):\n",
    "            if not son[x]:\n",
    "                return 1, 1\n",
    "            res = 1\n",
    "            total = 0\n",
    "            for y in son[x]:\n",
    "                a, b = dfs(y)\n",
    "                res = res * comb(total + b, b) % mod * a % mod\n",
    "                total += b\n",
    "            return res, total + 1\n",
    "        mod = 10 ** 9 + 7\n",
    "        return dfs(0)[0]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToBuildRooms(self, prevRoom: List[int]) -> int:\n",
    "        n = len(prevRoom)\n",
    "        g = [[] for _ in range(n)]\n",
    "        for i in range(1,n): g[prevRoom[i]].append(i)\n",
    "        mod = 1000000007\n",
    "\n",
    "        def dfs(x):\n",
    "            if not g[x]: return 1,1\n",
    "            cnt,score = 0,1\n",
    "            for y in g[x]:\n",
    "                c,s = dfs(y)\n",
    "                cnt += c\n",
    "                score = score*s*comb(cnt,c)%mod\n",
    "            cnt += 1\n",
    "            return cnt,score\n",
    "        \n",
    "        return dfs(0)[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = int(1e9 + 7)\n",
    "N = int(1e5 + 10)\n",
    "fac = [1] * N\n",
    "ifac = [1] * N\n",
    "for i in range(1, N):\n",
    "    fac[i] = (fac[i - 1] * i) % MOD\n",
    "    ifac[i] = (ifac[i - 1] * pow(i, MOD - 2, MOD)) % MOD\n",
    "\n",
    "def C(n: int, k: int) -> int:  #不重复组合数，n个不同物品不重复无序的取出k个\n",
    "    if n < 0 or k < 0 or n < k:\n",
    "        return 0\n",
    "    return ((fac[n] * ifac[k]) % MOD * ifac[n - k]) % MOD\n",
    "class Solution:\n",
    "    def waysToBuildRooms(self, prevRoom: List[int]) -> int:\n",
    "        n=len(prevRoom)\n",
    "        g=[[] for _ in range(n)]\n",
    "        for i,f in enumerate(prevRoom):\n",
    "            if f!=-1:\n",
    "                g[f].append(i)\n",
    "        def dfs(u):\n",
    "            ra=ta=0\n",
    "            for v in g[u]:\n",
    "                rb,tb=dfs(v)\n",
    "                if ra==0:\n",
    "                    ra+=rb\n",
    "                    ta+=tb\n",
    "                else:\n",
    "                    ra=ra*rb*C(ta+tb,ta)%MOD\n",
    "                    ta+=tb            \n",
    "            return [1,ra][ra>0],ta+1 \n",
    "        \n",
    "        return dfs(0)[0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# prevRoom gave a tree structure of n rooms\r\n",
    "# dp[i] := ways to build subtree rooted at node i\r\n",
    "# dp[i] = 1 if i is a leaf node, i.e. prevRoom[j] != i for 0 <= j < n\r\n",
    "# assume subtree i has size of sz[i], ways to build this subtree is to\r\n",
    "# select sz[j] position out of sz[i] - 1 total positions, times dp[j]\r\n",
    "# select sz[k] position out of sz[i] - sz[j] - 1 total positions, times dp[k]\r\n",
    "# ...\r\n",
    "# j, k, .. is subtrees of node i\r\n",
    "from math import comb\r\n",
    "class Solution:\r\n",
    "    def waysToBuildRooms(self, prevRoom: List[int]) -> int:\r\n",
    "        n = len(prevRoom)\r\n",
    "        dp = [1] * n\r\n",
    "        sz = [1] * n\r\n",
    "        children: list[list[int]] = [[] for _ in range(n)]\r\n",
    "        for i in range(1, n):\r\n",
    "            children[prevRoom[i]].append(i)\r\n",
    "        \r\n",
    "        def postorder(node: int) -> None:\r\n",
    "            for child in children[node]:\r\n",
    "                postorder(child)\r\n",
    "                sz[node] += sz[child]\r\n",
    "            \r\n",
    "            vac = sz[node] - 1\r\n",
    "            for child in children[node]:\r\n",
    "                dp[node] *= comb(vac, sz[child]) * dp[child]\r\n",
    "                dp[node] %= 1000000007\r\n",
    "                vac -= sz[child]\r\n",
    "        \r\n",
    "        postorder(0)\r\n",
    "        return dp[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# prevRoom gave a tree structure of n rooms\r\n",
    "# dp[i] := ways to build subtree rooted at node i\r\n",
    "# dp[i] = 1 if i is a leaf node, i.e. prevRoom[j] != i for 0 <= j < n\r\n",
    "# assume subtree i has size of sz[i], ways to build this subtree is to\r\n",
    "# select sz[j] position out of sz[i] - 1 total positions, times dp[j]\r\n",
    "# select sz[k] position out of sz[i] - sz[j] - 1 total positions, times dp[k]\r\n",
    "# ...\r\n",
    "# j, k, .. is subtrees of node i\r\n",
    "from math import comb\r\n",
    "class Solution:\r\n",
    "    def waysToBuildRooms(self, prevRoom: List[int]) -> int:\r\n",
    "        n = len(prevRoom)\r\n",
    "        dp = [1] * n\r\n",
    "        sz = [1] * n\r\n",
    "        children: list[list[int]] = [[] for _ in range(n)]\r\n",
    "        for i in range(1, n):\r\n",
    "            children[prevRoom[i]].append(i)\r\n",
    "        \r\n",
    "        def postorder(node: int) -> None:\r\n",
    "            for child in children[node]:\r\n",
    "                postorder(child)\r\n",
    "                sz[node] += sz[child]\r\n",
    "                dp[node] *= comb(sz[node] - 1, sz[child]) * dp[child]\r\n",
    "                dp[node] %= 1000000007\r\n",
    "            \r\n",
    "        postorder(0)\r\n",
    "        return dp[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    mod = int(1e9 + 7)\n",
    "\n",
    "    def waysToBuildRooms(self, prevRoom: List[int]) -> int:\n",
    "        n = len(prevRoom)\n",
    "        self.factorial, self.inv = [1] * n, [1] * n\n",
    "        for i in range(1, n):\n",
    "            self.factorial[i] = (self.factorial[i - 1] * (i + 1)) % self.mod\n",
    "        self.inv[-1] = self.quick(self.factorial[-1], self.mod - 2)  \n",
    "        for i in range(n - 2, -1, -1):\n",
    "            self.inv[i] = (self.inv[i + 1] * (i + 2)) % self.mod\n",
    "        assert self.inv[0] == 1, \"inv\"\n",
    "        self.children = [[] for i in range(n)]\n",
    "        self.deg = [0] * n\n",
    "        for i in range(n):\n",
    "            if (prevRoom[i] > -1): self.children[prevRoom[i]].append(i)\n",
    "        self.ans = [0] * n\n",
    "        self.dfs(0)\n",
    "\n",
    "        return self.ans[0]\n",
    "\n",
    "    def quick(self, base, p):\n",
    "        ans = 1\n",
    "        while (p > 0):\n",
    "            if (p % 2 == 1): ans = (ans * base) % self.mod\n",
    "            p = p // 2\n",
    "            base = (base * base) % self.mod\n",
    "        return ans\n",
    "\n",
    "    def dfs(self, index):\n",
    "        if self.ans[index] > 0 : return\n",
    "        if len(self.children[index]) == 0:\n",
    "            self.ans[index] = 1\n",
    "            self.deg[index] = 1\n",
    "            return\n",
    "        d, ways = 0, 1\n",
    "        for i in self.children[index]:\n",
    "            self.dfs(i)\n",
    "            d += self.deg[i]\n",
    "        ways = self.factorial[d - 1]\n",
    "        for i in self.children[index]:\n",
    "            ways = (ways * self.inv[self.deg[i] - 1]) % self.mod\n",
    "            ways = (ways * self.ans[i]) % self.mod\n",
    "        self.ans[index] = ways\n",
    "        self.deg[index] = d + 1\n",
    "        return\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToBuildRooms(self, prevRoom: List[int]) -> int:\n",
    "        connect = defaultdict(list)\n",
    "        for i,num in enumerate(prevRoom):\n",
    "            connect[num].append(i)\n",
    "\n",
    "        # 返回:元素个数,拓扑排序方案数\n",
    "        def dfs(idx):\n",
    "            nodes, ans = 0, 1\n",
    "            for subnode in connect[idx]:\n",
    "                nodes_, ans_ = dfs(subnode)\n",
    "                nodes += nodes_\n",
    "                # 因为当前的拓扑排序方案数不影响加入该子树后的拓扑排序方案数，所以是乘法叠加\n",
    "                # 新的拓扑排序方案数为: 当前的拓扑排序方案数 * 从nodes个位置里选nodes_个位置分配给该子树 * 子树的拓扑排序方案数\n",
    "                ans = (ans * comb(nodes, nodes_) * ans_) % (10 ** 9 + 7)\n",
    "            # 加上根节点\n",
    "            return nodes + 1, ans\n",
    "        \n",
    "        return dfs(0)[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def waysToBuildRooms(self, prevRoom: List[int]) -> int:\n",
    "        MOD = 1000000007\n",
    "        n = len(prevRoom)\n",
    "        nextRooms = [[] for _ in range(n)]\n",
    "        for i in range(1, n):\n",
    "            nextRooms[prevRoom[i]].append(i)\n",
    "\n",
    "        def dfs(room):\n",
    "            res = 1\n",
    "            nums = []\n",
    "            for next in nextRooms[room]:\n",
    "                cnt, num = dfs(next)\n",
    "                res *= cnt\n",
    "                res %= MOD\n",
    "                nums.append(num)\n",
    "            total = sum(nums)\n",
    "            for n in nums:\n",
    "                res *= comb(total, n)\n",
    "                total -= n\n",
    "                res %= MOD\n",
    "            return res, sum(nums)+1\n",
    "        res, _ = dfs(0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToBuildRooms(self, prevRoom: List[int]) -> int:\n",
    "\n",
    "        mod = 10 ** 9 + 7\n",
    "        ans = 1\n",
    "        g = defaultdict(list)\n",
    "        # ind = [0] * len(prevRoom)\n",
    "        for i, p in enumerate(prevRoom):\n",
    "            if p != -1:\n",
    "                g[p].append(i)\n",
    "                # ind[p] += 1\n",
    "        \n",
    "        def dfs(root):\n",
    "            \n",
    "            ans = 1\n",
    "            tot_cnt = 0\n",
    "            can = []\n",
    "            for nei in g[root]:\n",
    "                res, cnt = dfs(nei)\n",
    "                tot_cnt += cnt\n",
    "                can.append([res, cnt])\n",
    "            cur = tot_cnt\n",
    "            for a, b in can:\n",
    "                ans = ans * a * comb(cur, b) % mod\n",
    "                cur -= b\n",
    "            tot_cnt += 1\n",
    "            return ans, tot_cnt\n",
    "\n",
    "        return dfs(0)[0]\n",
    "\n",
    "\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToBuildRooms(self, prevRoom: List[int]) -> int:\n",
    "        n = len(prevRoom)\n",
    "        mod = 10 ** 9 + 7\n",
    "        dp = [0] * n\n",
    "        dp[0] = 1\n",
    "        from collections import defaultdict\n",
    "        from math import factorial\n",
    "        graph = defaultdict(list)\n",
    "        for i, r in enumerate(prevRoom):\n",
    "            if i > 0:\n",
    "                graph[r].append(i)\n",
    "        def dfs(u):\n",
    "            if u not in graph:\n",
    "                return [1, 1]\n",
    "            res = []\n",
    "            cnt = 0\n",
    "            for v in graph[u]:\n",
    "                tmp = dfs(v)\n",
    "                res.append(tmp)\n",
    "                cnt += tmp[1]\n",
    "            ans = [1, cnt + 1]\n",
    "            for a, b in res:\n",
    "                ans[0] *= a * math.comb(cnt, b)\n",
    "                ans[0] %= mod\n",
    "                cnt -= b\n",
    "            return ans\n",
    "        return dfs(0)[0]\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToBuildRooms(self, prevRoom: List[int]) -> int:\n",
    "        n = len(prevRoom)\n",
    "        mod = 10 ** 9 + 7\n",
    "        dp = [0] * n\n",
    "        dp[0] = 1\n",
    "        from collections import defaultdict\n",
    "        graph = defaultdict(list)\n",
    "        for i, r in enumerate(prevRoom):\n",
    "            if i > 0:\n",
    "                graph[r].append(i)\n",
    "        def dfs(u):\n",
    "            if u not in graph:\n",
    "                return [1, 1]\n",
    "            res = []\n",
    "            cnt = 0\n",
    "            for v in graph[u]:\n",
    "                tmp = dfs(v)\n",
    "                res.append(tmp)\n",
    "                cnt += tmp[1]\n",
    "            ans = [1, cnt + 1]\n",
    "            for a, b in res:\n",
    "                ans[0] *= a * math.comb(cnt, b)\n",
    "                ans[0] %= mod\n",
    "                cnt -= b\n",
    "            return ans\n",
    "        return dfs(0)[0]\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "from collections import defaultdict\n",
    "\n",
    "\n",
    "MOD = 10**9+7\n",
    "\n",
    "\n",
    "class Solution:\n",
    "  def waysToBuildRooms(self, prevRoom: List[int]) -> int:\n",
    "    # 建图记录父节点的子节点列表\n",
    "    dct = defaultdict(list)\n",
    "    for i, room in enumerate(prevRoom):\n",
    "      dct[room].append(i)\n",
    "\n",
    "    # 动态规划返回子树方案数与子树节点个数\n",
    "    def dfs(pre):\n",
    "      # 遇到叶子节点则此时只有一种方案\n",
    "      if not dct[pre]:\n",
    "        return [1, 1]\n",
    "      # 遍历计算每个子节点的子树方案数与子树节点个数\n",
    "      res = []\n",
    "      cnt = 0\n",
    "      for nex in dct[pre]:\n",
    "        cur = dfs(nex)\n",
    "        res.append(cur)\n",
    "        cnt += cur[1]\n",
    "      # 综合各个节点使用组合数学进行方案计算\n",
    "      ans = [1, cnt+1]\n",
    "      for a, b in res:\n",
    "        ans[0] *= a*math.comb(cnt, b)\n",
    "        cnt -= b\n",
    "        ans[0] %= MOD\n",
    "      return ans\n",
    "\n",
    "    return dfs(0)[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToBuildRooms(self, prevRoom: List[int]) -> int:\n",
    "        g = defaultdict(list) \n",
    "        n = len(prevRoom) \n",
    "        for i in range(1, n):\n",
    "            g[prevRoom[i]].append(i)\n",
    "        Mod = int(1e9+7)\n",
    "        def dfs(u):\n",
    "            dp = []\n",
    "            sz = [] \n",
    "            for v in g[u]:\n",
    "                a, b = dfs(v) \n",
    "                dp.append(a)\n",
    "                sz.append(b) \n",
    "            a, b = 1, sum(sz)\n",
    "            acc = 0\n",
    "            #print(dp, sz, a, b) \n",
    "            for dpi, szi in zip(dp, sz):\n",
    "                a *= dpi * math.comb(b - acc, szi) \n",
    "                a %= Mod \n",
    "                acc += szi\n",
    "            #rint(a, b+1) \n",
    "            return a, b + 1 \n",
    "        ans, _ = dfs(0) \n",
    "        return ans \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "mod = 10**9 + 7\n",
    "\n",
    "\n",
    "@cache\n",
    "def f(x):\n",
    "    if x <= 1:\n",
    "        return 1\n",
    "    return x * f(x - 1) % mod\n",
    "\n",
    "\n",
    "@cache\n",
    "def inv(x):\n",
    "    return pow(f(x), mod - 2, mod)\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def waysToBuildRooms(self, prevRoom: List[int]) -> int:\n",
    "        n = len(prevRoom)\n",
    "        g = [[] for _ in range(n)]\n",
    "\n",
    "        for x, y in enumerate(prevRoom):\n",
    "            if x != 0:\n",
    "                g[y].append(x)\n",
    "        size = [1] * n\n",
    "\n",
    "        def dfs(x):\n",
    "            cur = 1\n",
    "            for y in g[x]:\n",
    "                sub = dfs(y)\n",
    "                cur = cur * sub * inv(size[y]) % mod\n",
    "                size[x] += size[y]\n",
    "            return f(size[x] - 1) * cur % mod\n",
    "\n",
    "        return dfs(0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToBuildRooms(self, prevRoom: List[int]) -> int:\n",
    "        ad=collections.defaultdict(list)\n",
    "        MOD=10**9+7\n",
    "        for i,v in enumerate(prevRoom):\n",
    "            ad[v].append(i)\n",
    "        \n",
    "        def dfs(pre):\n",
    "            if not ad[pre]:\n",
    "                return [1,1]\n",
    "            cnt=0\n",
    "            res=[]\n",
    "            for nex in ad[pre]:\n",
    "                cur=dfs(nex)\n",
    "                cnt=cnt+cur[1]\n",
    "                res.append(cur)\n",
    "            ans=[1,cnt+1]\n",
    "            #print(res)\n",
    "            for a,b in res:\n",
    "                #ans[0]=ans[0]*a*math.factorial(cnt)//(math.factorial(b)*math.factorial(cnt-b))\n",
    "                ans[0]=ans[0]*a*math.comb(cnt,b)\n",
    "                cnt=cnt-b\n",
    "                ans[0]=ans[0]%MOD\n",
    "            return ans\n",
    "\n",
    "        return dfs(0)[0]\n",
    "\n",
    "\n",
    "        \n",
    "       \n",
    "      #  return dfs(0)[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToBuildRooms(self, prevRoom: List[int]) -> int:\n",
    "        ad=collections.defaultdict(list)\n",
    "        MOD=10**9+7\n",
    "        for i,v in enumerate(prevRoom):\n",
    "            ad[v].append(i)\n",
    "        \n",
    "        def dfs(pre):\n",
    "            if not ad[pre]:\n",
    "                return [1,1]\n",
    "            cnt=0\n",
    "            res=[]\n",
    "            for nex in ad[pre]:\n",
    "                cur=dfs(nex)\n",
    "                cnt=cnt+cur[1]\n",
    "                res.append(cur)\n",
    "            ans=[1,cnt+1]\n",
    "            print(res)\n",
    "            for a,b in res:\n",
    "                #ans[0]=ans[0]*a*math.factorial(cnt)//(math.factorial(b)*math.factorial(cnt-b))\n",
    "                ans[0]=ans[0]*a*math.comb(cnt,b)\n",
    "                cnt=cnt-b\n",
    "                ans[0]=ans[0]%MOD\n",
    "            return ans\n",
    "\n",
    "        return dfs(0)[0]\n",
    "\n",
    "\n",
    "        \n",
    "       \n",
    "      #  return dfs(0)[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "mod_number = 10 ** 9 + 7\n",
    "factorial = [1, 1]\n",
    "inv = [1, 1]\n",
    "for i in range(2, 100001):\n",
    "    factorial.append((factorial[-1] * i) % mod_number)\n",
    "    inv.append(pow(factorial[-1], -1, mod_number))\n",
    "\n",
    "class Solution:\n",
    "    def waysToBuildRooms(self, prevRoom: List[int]) -> int:\n",
    "        ans = [1]\n",
    "        nxt_dict = defaultdict(list)\n",
    "        for child, parent in enumerate(prevRoom):\n",
    "            nxt_dict[parent].append(child)\n",
    "\n",
    "        def helper(cur):\n",
    "            count_list = []\n",
    "            for nxt in nxt_dict[cur]:\n",
    "                count_list.append(helper(nxt))\n",
    "            child_count = sum(count_list)\n",
    "            ans[0] = (ans[0] * factorial[child_count]) % mod_number\n",
    "            for count in count_list:\n",
    "                ans[0] = (ans[0] * inv[count]) % mod_number\n",
    "            return child_count + 1\n",
    "\n",
    "        helper(0)\n",
    "        return ans[0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Combinatorics:\n",
    "    def __init__(self, n, mod):\n",
    "        # 模板：求全排列组合数，使用时注意 n 的取值范围\n",
    "        n += 10\n",
    "        self.perm = [1] * n\n",
    "        self.rev = [1] * n\n",
    "        self.mod = mod\n",
    "        for i in range(1, n):\n",
    "            # 阶乘数 i! 取模\n",
    "            self.perm[i] = self.perm[i - 1] * i\n",
    "            self.perm[i] %= self.mod\n",
    "        self.rev[-1] = self.mod_reverse(self.perm[-1], self.mod)  # 等价于pow(self.perm[-1], -1, self.mod)\n",
    "        for i in range(n - 2, 0, -1):\n",
    "            self.rev[i] = (self.rev[i + 1] * (i + 1) % mod)  # 阶乘 i! 取逆元\n",
    "        self.fault = [0] * n\n",
    "        self.fault_perm()\n",
    "        return\n",
    "\n",
    "    def ex_gcd(self, a, b):\n",
    "        # 扩展欧几里得求乘法逆元\n",
    "        if b == 0:\n",
    "            return 1, 0, a\n",
    "        else:\n",
    "            x, y, q = self.ex_gcd(b, a % b)\n",
    "            x, y = y, (x - (a // b) * y)\n",
    "            return x, y, q\n",
    "\n",
    "    def mod_reverse(self, a, p):\n",
    "        x, y, q = self.ex_gcd(a, p)\n",
    "        if q != 1:\n",
    "            raise Exception(\"No solution.\")   # 逆元要求a与p互质\n",
    "        else:\n",
    "            return (x + p) % p  # 防止负数\n",
    "\n",
    "    def comb(self, a, b):\n",
    "        if a < b:\n",
    "            return 0\n",
    "        # 组合数根据乘法逆元求解\n",
    "        res = self.perm[a] * self.rev[b] * self.rev[a - b]\n",
    "        return res % self.mod\n",
    "\n",
    "    def factorial(self, a):\n",
    "        # 组合数根据乘法逆元求解\n",
    "        res = self.perm[a]\n",
    "        return res % self.mod\n",
    "\n",
    "    def fault_perm(self):\n",
    "        # 求错位排列组合数\n",
    "        self.fault[0] = 1\n",
    "        self.fault[2] = 1\n",
    "        for i in range(3, len(self.fault)):\n",
    "            self.fault[i] = (i - 1) * (self.fault[i - 1] + self.fault[i - 2])\n",
    "            self.fault[i] %= self.mod\n",
    "        return\n",
    "\n",
    "    def inv(self, n):\n",
    "        # 求 pow(n, -1, mod)\n",
    "        return self.perm[n - 1] * self.rev[n] % self.mod\n",
    "\n",
    "    def catalan(self, n):\n",
    "        # 求卡特兰数\n",
    "        return (self.comb(2 * n, n) - self.comb(2 * n, n - 1)) % self.mod\n",
    "\n",
    "mod = 10**9 + 7\n",
    "cb = Combinatorics(10**5, mod)\n",
    "\n",
    "class Solution:\n",
    "    def waysToBuildRooms(self, prevRoom: List[int]) -> int:\n",
    "        n = len(prevRoom)\n",
    "        dct = [[] for _ in range(n)]\n",
    "        \n",
    "        degree = [0]*n\n",
    "        for i in range(1, n):\n",
    "            dct[prevRoom[i]].append(i)\n",
    "            degree[i] += 1\n",
    "        \n",
    "        def dfs(x):\n",
    "            res = []\n",
    "            for y in dct[x]: \n",
    "                res.append(dfs(y))\n",
    "            if not res:\n",
    "                return [1, 1]\n",
    "            cnt = sum(x for x, _ in res)\n",
    "            ss = cnt\n",
    "            ans = 1\n",
    "            for x, y in res:\n",
    "                ans *= cb.comb(cnt, x)\n",
    "                cnt -= x\n",
    "                ans %= mod\n",
    "                ans *= y\n",
    "                ans %= mod\n",
    "            return [ss+1, ans]\n",
    "        \n",
    "        return dfs(0)[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToBuildRooms(self, prevRoom: List[int]) -> int:\n",
    "        g = defaultdict(list) \n",
    "        n = len(prevRoom) \n",
    "        for i in range(1, n):\n",
    "            g[prevRoom[i]].append(i)\n",
    "        Mod = int(1e9+7)\n",
    "        fact = [1] * (n+1) \n",
    "        for i in range(2, n+1):\n",
    "            fact[i] = (i * fact[i-1])%Mod \n",
    "        def dfs(u):\n",
    "            dp = []\n",
    "            sz = [] \n",
    "            for v in g[u]:\n",
    "                a, b = dfs(v) \n",
    "                dp.append(a)\n",
    "                sz.append(b) \n",
    "            b = sum(sz)\n",
    "            a = fact[b] \n",
    "            for dpi, szi in zip(dp, sz):\n",
    "                inv = pow(fact[szi], Mod-2, Mod)\n",
    "                a = (a * dpi * inv) % Mod  \n",
    "            return a, b+1\n",
    "        ans, _ = dfs(0) \n",
    "        return ans \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToBuildRooms(self, prevRoom: List[int]) -> int:\n",
    "        n = len(prevRoom)\n",
    "        fac = [1]\n",
    "        inv = [1]\n",
    "        mod = 10 ** 9 + 7\n",
    "        for i in range(1, n):\n",
    "            fac.append(fac[-1] * i % mod)\n",
    "            inv.append(pow(fac[i], mod - 2, mod))\n",
    "        graph = collections.defaultdict(list)\n",
    "        for i in range(1, n):\n",
    "            graph[prevRoom[i]].append(i)\n",
    "        size = [1] * n \n",
    "        res = [1] * n \n",
    "        def dfs(node):\n",
    "            for nei in graph[node]:\n",
    "                dfs(nei)\n",
    "                size[node] += size[nei]\n",
    "                res[node] = res[node] * res[nei] * inv[size[nei]] % mod \n",
    "            res[node] = res[node] * fac[size[node] - 1] % mod \n",
    "        dfs(0)\n",
    "        return res[0]\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToBuildRooms(self, prevRoom: List[int]) -> int:\n",
    "        n = len(prevRoom)\n",
    "        fac = [1]\n",
    "        inv = [1]\n",
    "        mod = 10 ** 9 + 7\n",
    "        for i in range(1, n):\n",
    "            fac.append(fac[-1] * i % mod)\n",
    "            inv.append(pow(fac[i], mod - 2, mod))\n",
    "        graph = collections.defaultdict(list)\n",
    "        for i in range(1, n):\n",
    "            graph[prevRoom[i]].append(i)\n",
    "        size = [1] * n \n",
    "        res = [1] * n \n",
    "        def dfs(node):\n",
    "            for nei in graph[node]:\n",
    "                dfs(nei)\n",
    "                size[node] += size[nei]\n",
    "                res[node] = res[node] * res[nei] * inv[size[nei]] % mod \n",
    "            res[node] = res[node] * fac[size[node] - 1] % mod \n",
    "        dfs(0)\n",
    "        return res[0]\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToBuildRooms(self, prevRoom: List[int]) -> int:\n",
    "        g = defaultdict(list) \n",
    "        n = len(prevRoom) \n",
    "        for i in range(1, n):\n",
    "            g[prevRoom[i]].append(i)\n",
    "        Mod = int(1e9+7)\n",
    "        fact = [1] * (n+1) \n",
    "        for i in range(2, n+1):\n",
    "            fact[i] = (i * fact[i-1])%Mod \n",
    "        def dfs(u):\n",
    "            dp = []\n",
    "            sz = [] \n",
    "            for v in g[u]:\n",
    "                a, b = dfs(v) \n",
    "                dp.append(a)\n",
    "                sz.append(b) \n",
    "            a, b = 1, sum(sz)\n",
    "            acc = 0 \n",
    "            for dpi, szi in zip(dp, sz):\n",
    "                inv = pow(fact[szi], Mod-2, Mod)\n",
    "                a = (a * dpi * inv) % Mod  \n",
    "            \n",
    "            return (a*fact[b]) % Mod, b + 1 \n",
    "        ans, _ = dfs(0) \n",
    "        return ans \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToBuildRooms(self, prevRoom: List[int]) -> int:\n",
    "        mod = 10**9 + 7\n",
    "        \n",
    "        n = len(prevRoom)\n",
    "        # fac[i] 表示 i!\n",
    "        # inv[i] 表示 i! 的乘法逆元\n",
    "        fac, inv = [0] * n, [0] * n\n",
    "        fac[0] = inv[0] = 1\n",
    "        for i in range(1, n):\n",
    "            fac[i] = fac[i - 1] * i % mod\n",
    "            # 使用费马小定理计算乘法逆元\n",
    "            inv[i] = pow(fac[i], mod - 2, mod)\n",
    "        \n",
    "        # 构造树\n",
    "        edges = defaultdict(list)\n",
    "        for i in range(1, n):\n",
    "            edges[prevRoom[i]].append(i)\n",
    "        \n",
    "        f, cnt = [0] * n, [0] * n\n",
    "        \n",
    "        def dfs(u: int) -> None:\n",
    "            f[u] = 1\n",
    "            for v in edges[u]:\n",
    "                dfs(v)\n",
    "                # 乘以左侧的 f[ch] 以及右侧分母中 cnt[ch] 的乘法逆元\n",
    "                f[u] = f[u] * f[v] * inv[cnt[v]] % mod\n",
    "                cnt[u] += cnt[v]\n",
    "            # 乘以右侧分子中的 (cnt[i] - 1)!\n",
    "            f[u] = f[u] * fac[cnt[u]] % mod\n",
    "            cnt[u] += 1\n",
    "        \n",
    "        dfs(0)\n",
    "        return f[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def waysToBuildRooms(self, prevRoom: list[int]) -> int:\n",
    "        from collections import defaultdict\n",
    "\n",
    "        mod = 10**9 + 7\n",
    "        n = len(prevRoom)\n",
    "        # fac[i] 表示 i! % mod\n",
    "        # inv[i] 表示 i! 的乘法逆元 % mod\n",
    "        fac, inv = [0] * n, [0] * n\n",
    "        fac[0] = inv[0] = 1\n",
    "        for i in range(1, n):\n",
    "            fac[i] = fac[i - 1] * i % mod\n",
    "            # 使用费马小定理计算乘法逆元\n",
    "            inv[i] = pow(fac[i], mod - 2, mod)\n",
    "        \n",
    "        # 构造树\n",
    "        edges = defaultdict(list)\n",
    "        for i in range(1, n):\n",
    "            edges[prevRoom[i]].append(i)\n",
    "        \n",
    "        f, cnt = [0] * n, [0] * n\n",
    "        \n",
    "        def dfs(u: int) -> None:\n",
    "            f[u] = 1\n",
    "            for v in edges[u]:\n",
    "                dfs(v)\n",
    "                # 乘以左侧的 f[ch] 以及右侧分母中 cnt[ch] 的乘法逆元\n",
    "                f[u] = f[u] * f[v] * inv[cnt[v]] % mod\n",
    "                cnt[u] += cnt[v]\n",
    "            # 乘以右侧分子中的 (cnt[i] - 1)!\n",
    "            f[u] = f[u] * fac[cnt[u]] % mod\n",
    "            cnt[u] += 1\n",
    "        \n",
    "        dfs(0)\n",
    "        return f[0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "mx = 10 ** 5\n",
    "fact = [1] * (mx + 1)\n",
    "mod = 10 ** 9 + 7\n",
    "for i in range(2, mx + 1):\n",
    "    fact[i] = (fact[i - 1] * i) % mod \n",
    "    \n",
    "class Solution:\n",
    "    def waysToBuildRooms(self, prevRoom: List[int]) -> int:\n",
    "        n = len(prevRoom)\n",
    "        g = [[] for _ in range(n)]\n",
    "        for i, j in enumerate(prevRoom[1:], 1):\n",
    "            g[j].append(i)        \n",
    "        cnt = [0] * n \n",
    "        \n",
    "        def dfs(node):\n",
    "            if len(g[node]) == 0:\n",
    "                cnt[node] = 1\n",
    "                return 1\n",
    "            res = 0\n",
    "            for nxt in g[node]:\n",
    "                res += dfs(nxt)\n",
    "            cnt[node] = res + 1\n",
    "            return cnt[node]\n",
    "        \n",
    "        dfs(0)\n",
    "\n",
    "        @cache\n",
    "        def f(node):\n",
    "            if len(g[node]) == 0:                \n",
    "                return 1\n",
    "            \n",
    "            tot = cnt[node] - 1\n",
    "            ans = fact[tot]\n",
    "            for nxt in g[node]:                \n",
    "                ans *= pow(fact[cnt[nxt]], -1, mod) * f(nxt)\n",
    "                # ans %= mod \n",
    "            return ans % mod \n",
    "        \n",
    "        return f(0)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "mx = 10 ** 5\n",
    "fact = [1] * (mx + 1)\n",
    "mod = 10 ** 9 + 7\n",
    "for i in range(2, mx + 1):\n",
    "    fact[i] = (fact[i - 1] * i) % mod \n",
    "    \n",
    "class Solution:\n",
    "    def waysToBuildRooms(self, prevRoom: List[int]) -> int:\n",
    "        n = len(prevRoom)\n",
    "        g = [[] for _ in range(n)]\n",
    "        for i, j in enumerate(prevRoom[1:], 1):\n",
    "            g[j].append(i)        \n",
    "        cnt = [0] * n \n",
    "        \n",
    "        def dfs(node):\n",
    "            if len(g[node]) == 0:\n",
    "                cnt[node] = 1\n",
    "                return 1\n",
    "            res = 0\n",
    "            for nxt in g[node]:\n",
    "                res += dfs(nxt)\n",
    "            cnt[node] = res + 1\n",
    "            return cnt[node]\n",
    "        \n",
    "        dfs(0)\n",
    "\n",
    "        @cache\n",
    "        def f(node):\n",
    "            if len(g[node]) == 0:                \n",
    "                return 1\n",
    "            \n",
    "            tot = cnt[node] - 1\n",
    "            ans = fact[tot]\n",
    "            for nxt in g[node]:                \n",
    "                ans *= pow(fact[cnt[nxt]], -1, mod) * f(nxt)\n",
    "                ans %= mod \n",
    "            return ans % mod \n",
    "        \n",
    "        return f(0)\n",
    "        "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
